
Split-Merge Treap

\hr

\subsubsection{对于无旋 Treap 的提示}

看楼上的  Treap 词条 

\textbf{OI 常用的可持久化平衡树} 一般就是 \textbf{可持久化无旋转 Treap} 所以推荐首先学习楼上的 \textbf{无旋转 Treap}

\subsubsection{思想 / 做法}

我们来看看旋转的 Treap，为什么不能可持久化呢？

如果带旋转，那么就会\textbf{破环原有的父子关系}，破环原有的路径和树形态，这是可持久化无法接受的。

如果把 Treap 变为非旋转的，我们发现可以通过可持久化 \textbf{Merge} 和 \textbf{Split} 操作就可以完成可持久化.

「一切可支持操作都可以通过 \textbf{Merge} \textbf{Split} \textbf{Newnode} \textbf{Build} 完成」，而 \textbf{Build} 操作只用于建造无需理会，\textbf{Newnode}（新建节点） 就是用来可持久化的工具。

我们来观察一下 \textbf{Merge} 和 \textbf{Split} ，我们会发现它们都是由上而下的操作！

因此我们完全可以\textbf{参考线段树的可持久化操作}对它进行可持久化。

\subsubsection{可持久化操作}

\textbf{可持久化}是对\textbf{数据结构}的一种操作，即保留历史信息，使得在后面可以调用之前的历史版本.

对于\textbf{可持久化线段树}来说，每一次新建历史版本就是把\textbf{沿途的修改路径}复制出来

那么对可持久化 Treap (目前国内 OI 常用的版本) 来说：

在复制一个节点 $X_{a}$($X$ 节点的第 $a$ 个版本) 的新版本 $X_{a+1}$ ($X$ 节点的第 $a+1$ 个版本) 以后：

\begin{itemize}
\item 如果某个儿子节点 $Y$ 不用修改信息，那么就把 $X_{a+1}$ 的指针直接指向 $Y_{a}$ ($Y$ 节点的第 $a$ 个版本) 即可。
\item 反之，如果要修改 $Y$ ，那么就在\textbf{递归到下层}时\textbf{新建} $Y_{a+1}$ ($Y$ 节点的第 $a+1$ 个版本) 这个新节点用于\textbf{存储新的信息}，同时把 $X_{a+1}$ 的指针指向 $Y_{a+1}$ ($Y$ 节点的第 $a+1$ 个版本)。
\end{itemize}

\subsubsection{可持久化}

需要的东西:

\begin{itemize}
\item 一个 struct 数组 存\textbf{每个节点}的信息 (一般叫做 tree 数组)； (当然写\textbf{指针版}平衡树的大佬就可以考虑不用这个数组了)
\item 一个\textbf{根节点数组}，存每个版本的{\em 树根 }，每次查询版本信息时就从\textbf{根数组存的节点}开始；
\item split() 分裂 \textbf{从树中分裂出两棵树}
\item merge() 合并 \textbf{把两棵树按照随机权值合并}
\item newNode() 新建一个节点
\item build() 建树
\end{itemize}

\paragraph{Split}

对于\textbf{分裂操作}，每次分裂路径时\textbf{新建节点}指向分出来的路径，用 std::pair 存新分裂出来的两棵树的根。

std::pair \&lt;int,int> split(x,k) 返回一个 std::pair;

表示把 $_x$ 为根的树的前 $k$ 个元素放在\textbf{一棵树}中，剩下的节点构成在另一棵树中，返回这两棵树的根（first 是第一棵树的根，second 是第二棵树的）。

\begin{itemize}
\item 如果 $x$ 的\textbf{左子树}的 $key ≥ k$，那么\textbf{直接递归进左子树}，把左子树分出来的第二颗树和当前的 x \textbf{右子树}合并。
\item 否则递归\textbf{右子树}。
\end{itemize}

\begin{cppcode}
static std::pair<int, int> _split(int _x, int k) {
  if (_x == 0)
    return std::make_pair(0, 0);
  else {
    int _vs = ++_cnt;  //新建节点（可持久化的精髓）
    _trp[_vs] = _trp[_x];
    std::pair<int, int> _y;
    if (_trp[_vs].key <= k) {
      _y = _split(_trp[_vs].leaf[1], k);
      _trp[_vs].leaf[1] = _y.first;
      _y.first = _vs;
    } else {
      _y = _split(_trp[_vs].leaf[0], k);
      _trp[_vs].leaf[0] = _y.second;
      _y.second = _vs;
    }
    _trp[_vs]._update();
    return _y;
  }
}
\end{cppcode}

\paragraph{Merge}

int merge(x,y) 返回 merge 出的树的根。

同样递归实现。如果 \textbf{x 的随机权值} > \textbf{y 的随机权值} ，则 $merge(x_{rc},y)$，否则 $merge(x,y_{lc})$。

\begin{cppcode}
static int _merge(int _x, int _y) {
  if (_x == 0 || _y == 0)
    return _x ^ _y;
  else {
    if (_trp[_x].fix < _trp[_y].fix) {
      _trp[_x].leaf[1] = _merge(_trp[_x].leaf[1], _y);
      _trp[_x]._update();
      return _x;
    } else {
      _trp[_y].leaf[0] = _merge(_x, _trp[_y].leaf[0]);
      _trp[_y]._update();
      return _y;
    }
  }
}
\end{cppcode}

\subsubsection{Luogu P3835 可持久化平衡树}

\paragraph{题目背景}

本题为题目 \textbf{普通平衡树} 的可持久化加强版。

数据已经经过强化

\paragraph{题目描述}

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）：

\begin{enumerate}
\item 插入 x 数
\item 删除 x 数（若有多个相同的数，因只删除一个，如果没有请忽略该操作）
\item 查询 x 数的排名（排名定义为比当前数小的数的个数 + 1。若有多个相同的数，因输出最小的排名）
\item 查询排名为 x 的数
\item 求 x 的前驱（前驱定义为小于 x，且最大的数，如不存在输出 -2147483647）
\item 求 x 的后继（后继定义为大于 x，且最小的数，如不存在输出 2147483647）
\end{enumerate}

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 3, 4, 5, 6 即保持原版本无变化）。

每个版本的编号即为操作的序号（版本 0 即为初始状态，空树）

\paragraph{输入格式}

第一行为 n，表示操作的个数, 下面 n 行每行有两个数 opt 和 x，opt 表示操作的序号 $(1 \leq x \leq  le6)$。

\paragraph{输出格式}

对于操作 3,4,5,6 每行输出一个数，表示对应答案。

\paragraph{题解简述}

就是\textbf{普通平衡树}一题的可持久化版，操作和该题类似..

只是使用了可持久化的 merge 和 split 操作

\subsubsection{推荐的练手题}

\begin{enumerate}
\item luogu P3919 可持久化数组 (模板题)
\item codeforces 702F T-shirt
\end{enumerate}

\subsubsection{另外}

\begin{enumerate}
\item 可持久化平衡树可以用来维护动态凸包，仙人掌等东西，如果读者有兴趣可以阅读相应的  \textbf{计算几何}  知识，再来食用。
\item Zip Tree 作为一种新的数据结构在 2018.8 月由 Robert E. Tarjan -  Caleb C. Levy - Stephen Timmel 提出，可以去了解一下\textasciitilde{}
\end{enumerate}
